⟸ pàgina anterior ⟸

Exercici 8 (Tasca 1).

(theory of languages, cardinality of languages)

Sobre la mida dels llenguatges

Justifiqueu les respostes a les preguntes següents.

1. Donats dos llenguatges L_1,L_2, és cert que |L_1|\cdot|L_2|=|L_1\cdot L_2|? I si L_1=L_2?
2. Donat un homomorfisme \sigma, és cert que si \sigma és injectiu, llavors |\sigma(L)|=|L|?
3. Donat un llenguatge L, és cert que |L^R|=|L|?
4. Donat un llenguatge L i un natural n, és cert que |L^n|=|L|^n?

Recordeu que una funció f és injectiva si f(x)=f(y) implica x=y.